package com.heima.leetcode.practice;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 560. 和为 K 的子数组
 * @date 2025/2/15 15:07
 */
public class E560 {

    /**
     * <h3>方法一：前缀和，时间复杂度O(N^2)</h3>
     *
     * @param nums 输入数组
     * @param k    目标值
     * @return 和为k的子数组个数
     */
    public int subarraySum1(int[] nums, int k) {
        // 1. 创建前缀和数组
        int count = 0;
        int[] preSum = new int[nums.length];
        // 2. 填充前缀和数组
        preSum[0] = nums[0];
        for (int i = 1; i < preSum.length; i++)
            preSum[i] = preSum[i - 1] + nums[i];
        // 3. 遍历前缀和数组，计算和为k的子数组个数
        for (int i = 0; i < preSum.length; i++) {
            // 3.1 判断当前前缀和是否等于k
            if (preSum[i] == k) count++;
            // 3.2 当前前缀和与k的差值
            int diff = preSum[i] - k;
            // 3.3 遍历前缀和数组，寻找和为k的子数组
            for (int j = 0; j < i; j++)
                if (preSum[j] == diff)
                    count++;
        }
        // 4. 返回和为k的子数组个数
        return count;
    }

    // 思考：方法一放在leetcode上效率并不快，怎么优化呢？
    // 在寻找和为k的子数组时，每次都要查询前缀和数组，大量的重复操作
    // 可以考虑统计前缀和出现的次数，用HashMap，但能不能填充完成之后去统计呢？

    /**
     * <h3>方法二：前缀和优化，时间复杂度O(N)</h3>
     *
     * @param nums 输入数组
     * @param k    目标值
     * @return 和为k的子数组个数
     */
    public int subarraySum2(int[] nums, int k) {
        int count = 0, prefixSum = 0;
        // 1. 准备哈希表，记录各个前缀和出现的次数，一定要边遍历边记录，不然找出来的prefixSum - k出现次数可能来自于后面
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        // 2. 填充哈希表，前缀和为0出现1次，用于处理当前前缀和就是k的情况（prefixSum - k == 0）
        prefixSumCount.put(0, 1);
        // 3. 遍历数组，计算前缀和，当前前缀和与k的差值是否在哈希表中存在
        for (int num : nums) {
            // 3.1 计算当前前缀和、计算当前前缀和与k的差值
            prefixSum += num;
            int diff = prefixSum - k;
            // 3.2 判断当前前缀和与k的差值是否在哈希表中存在，如果存在，则更新count
            if (prefixSumCount.containsKey(diff))
                count += prefixSumCount.get(diff);
            // 3.3 更新哈希表，记录当前前缀和出现的次数
            prefixSumCount.compute(prefixSum, (key, value) -> value == null ? 1 : value + 1);
        }
        // 4. 返回和为k的子数组个数
        return count;
    }
}
